\documentclass[12pt]{article}
\usepackage{times}
\usepackage{graphicx}
\usepackage{sidecap}
\usepackage{wrapfig}
\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\baselinestretch}{1.2}
\newenvironment{mylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}
\newenvironment{mylisting2}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

%%% This file is Open Content

\begin{document}
	\textbf{{\Huge 27-Trees, an extension on octrees - This file is open content}}
{\center{Dec 29, 2011, 
	Johan Ceuppens, Theo D'Hondt - Vrije Universiteit Brussel}}
\\
{\large{\textbf{\center Abstract}}}
\\
\\
\section{\large Introduction}

An octree is an eight-fold tree, a tree ADT with 8 nodes and/or leaves.
Every 3D object is contained inside the tree space. If we extend the
tree towards 27 cubes subdivided in cubes of 27 cubes and so on, we
gain a node system which has some
nice algorithms for containment and walkthrough using node depth.

The tree canbe used in several ways, you can use many trees for mountains
(plateaus, see fig. 1) or a big tree for the 3D world containers.
Note that much can be multi-threaded because there are propagator 
algorithms for tree (leaves and nodes) random walk algorithms.

\section{\large Walkthrough algorithm}

If you adjust the node.depth in a 27-tree you have the smallest 
modification for tree traversal, an integer change. You can change this
depth around the player character so he can walk down cliffs, to (lower)
platforms which do not collide because of the same node.depth.

\section{\large 27-Tree - a Python (Pygame) implementation}

\begin{mylisting}
\begin{verbatim}
# Copyright (C) Johan Ceuppens 2011-2012
# The code is public domain

from list import *
from engine import *
from pygame import *
from pygame.locals import *
import pygame

class OcttreeLeaf:
    "Octotree Leaf"
    def __init__(self, x,y,z,w,h,d,depth):
	self.x = x 
	self.y = y 
	self.z = z 
	self.w = w 
	self.h = h 
	self.d = d 
	self.depth = 0
	self.collide = 0 
	
    def isleaf(self):
	return 1

class OcttreeNode(OcttreeLeaf):
    "Octotree Node"
    def __init__(self,x,y,z,w,h,d,depth):
        OcttreeLeaf.__init__(self,x,y,z,w,h,d,depth)
	self.nodes = List() 
	self.collide = 0 

    def isleaf(self):
	return 0

    def add(self,n):
        self.nodes.addobject(n)


class Octtree:
    "Octtree"
    def __init__(self,x,y,z,w,h,d,depth,room):
	self.tree = OcttreeNode(x,y,z,w,h,d,depth)
	self.depth = depth
	self.room = room
	self.diagonaloffset = 120
        self.image = pygame.image.load("./pics/tile1-rot-420x420.bmp").convert()
        self.image.set_colorkey((0,0,0))
	
    def add(self,n):
        self.tree.addobject(n)

    def generatetree(self,border):
	self.generatetreerec(self.depth,self.tree,self.tree.x,self.tree.y,self.tree.z,self.tree.w,self.tree.h,self.tree.d,border)

    def generatetreerec(self,depth,node,x,y,z,w,h,d,border):
	if depth <= 0:
		for i in range(1,4):
			node.add(OcttreeLeaf(i*x/4,   y/4,    z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(i*x/4,   i*y/4,    z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(i*x/4,   i*y/4,    i*z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(x/4,   i*y/4,    z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(x/4,   i*y/4,    i*z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(i*x/4,   y/4,    i*z/4,    w/3,h/3,d/3,depth))
		for i in range(1,4):
			node.add(OcttreeLeaf(x/4,   y/4,    i*z/4,    w/3,h/3,d/3,depth))
		### center node
		for i in range(0,21):
			tempnode = node.nodes.getwithindex(i)	
			if border < tempnode.x + tempnode.w:
				border += border
				node.nodes.getwithindex(i).collide = 1
		return 
	for i in range(1,4):
		node.add(OcttreeNode(i*x/4,   y/4,    z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(i*x/4,   i*y/4,    z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(i*x/4,   i*y/4,    i*z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(x/4,   i*y/4,    z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(x/4,   i*y/4,    i*z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(i*x/4,   y/4,    i*z/4,    w/3,h/3,d/3,depth))
	for i in range(1,4):
		node.add(OcttreeNode(x/4,   y/4,    i*z/4,    w/3,h/3,d/3,depth))

	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i),i*x/4,    y/4,    z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+2),i*x/4,    i*y/4,    z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+5),i*x/4,    i*y/4,    i*z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+8),x/4,    i*y/4,    z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+11),x/4,    i*y/4,    i*z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+14),i*x/4,    y/4,    i*z/4,   w/3,h/3,d/3,border)
	for i in range(1,4):
		self.generatetreerec(depth-1,node.nodes.getwithindex(i+17),x/4,    y/4,    i*z/4,   w/3,h/3,d/3,border)

    def collision(self,player,game):
	self.result = 0
	self.collisionrec(self.depth,self.tree,player,game)
	return self.result

    def collisionx(self,player):
	self.result = 0
	self.collisionrecx(self.depth,self.tree,player.x,player.y,player.z)
	return self.result

    def collisiony(self,player):
	self.result = 0
	self.collisionrecy(self.depth,self.tree,player.x,player.y,player.z)
	return self.result

    def collisionrec(self,depth,node,player,game):
	x = player.x
	y = player.y
	z = player.z
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	if (x + relx < node.x +  node.w*(-depth+1) and x + relx + node.w > node.x) and (y + rely < node.y + node.h*(-depth+1) and y + rely > node.y):
		print "collision player.depth=%d map.depth=%d!" % (player.depth,depth)
		if depth <= player.depth: 
			self.result = 1
			return
		elif player.depth < depth:
		### NOTE2: This is for the actual walkthrough algorithm
		### 	  which changes the node depths in surrounding
		### 	  Nodes/Leaves when you jump off or on a cliff
		###	  (impassable terrain)			
		###	node.depth -= 1	
			self.result = 2
			return
		elif player.depth > depth:	
			self.result = 3
			return
		
		###return #NOTE3 do not return for each node to be switched
        else:		
		for i in range(0,21):
			if not node.isleaf():
	 			n = node.nodes.getwithindex(i)
				if n != None: 
					self.collisionrec(depth-1,n,player,game)
		return
	
    def collisionrecx(self,depth,node,x,y,z):
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	if node.isleaf():
		return
	for i in range(0,21):
		n = node.nodes.getwithindex(i)
		if (n != None):
			if (x < n.x + n.w and x > n.x): 
				print "collision!"
				if n.collide == 1:
					self.result = 1
					return
			self.collisionrecx(depth-1,n,x,y,z)	

    def collisionrecy(self,depth,node,x,y,z):
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	if node.isleaf():
		return
	for i in range(0,21):
		n = node.nodes.getwithindex(i)
		if (n != None):
			if (y < n.y + n.h and y > n.y): 
				print "collision!"
				if n.collide == 1:
					self.result = 1
					return
			self.collisionrecx(depth-1,n,x,y,z)	

    def walkin(self,player):
	self.result = 0
	self.walkinrec(self.depth,self.tree,player)
	return self.result

    def walkinrec(self,depth,node,player):
	px = player.x
	py = player.y
	pz = player.z
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	dd = self.depth-1 
	## SE dagonal orientation
	if rely == relx:
		self.result = 1	
		return
	if node.isleaf():
		print "leaf!"
		return
	for i in range(0,21):
		if node.nodes.getwithindex(i) != None:
			relx = self.room.roomman.room.relativex
			rely = self.room.roomman.room.relativey
			if px + self.room.roomman.room.relativex < node.nodes.getwithindex(i).x*(depth-1):
				self.walkinrec(depth-1,node.nodes.getwithindex(i),player)
   
    def draw(self,player,screen,rotx,roty,rotz):
	self.result = 0
	self.drawrec(self.depth,self.tree,player,rotx,roty,rotz)
	return self.result

    def drawrec(self,depth,node,player,rotx,roty,rotz):
	px = player.x
	py = player.y
	pz = player.z
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	dd = self.depth-1 
	if node.isleaf() and node.collide == 1:
		r1x = node.x	
		r1y = node.y 
		r1z = node.z
		r1w = node.w	
		r1h = node.h
		r1d = node.d

		for i in range(0,21):
			e = engine(rotx,roty,rotz)

			r1 = Vector3(node.x,node.y,node.z)
			r2 = Vector3(node.x,node.y,node.z)
			if rotx:
				r1 = e.mx.multiply(r1)
				r2 = e.mx.multiply(r2)
			if roty:
				r1 = e.my.multiply(r1)
				r2 = e.my.multiply(r2)
			if rotz:
				r1 = e.mz.multiply(r1)
				r2 = e.mz.multiply(r2)
			r1x = r1.array[0]	
			r1y = r1.array[1]	
			r1z = r1.array[2]	
			r2x = r2.array[0]	
			r2y = r2.array[1]	
			r2z = r2.array[2]
			color = (255,0,0)
			if node.collide:
				color = (0,0,255)
			pygame.draw.line(pygame.display.get_surface(), color, (r1x+relx,r1y+rely), (r2x+relx,r2y+rely))
       		pygame.display.get_surface().blit(self.image, (r1x+relx,r1y+rely))

	for i in range(0,21):
		if not node.isleaf() and node.nodes.getwithindex(i) != None:
			self.drawrec(depth-1,node.nodes.getwithindex(i),player,rotx,roty,rotz)

    def draw2(self,player,screen):
	self.result = 0
	self.drawrec2(self.depth,self.tree,player)
	return self.result

    def drawrec2(self,depth,node,player):
	px = player.x
	py = player.y
	pz = player.z
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	dd = self.depth-1 
	## SE dagonal orientation
	if node.isleaf():
		r1x = node.x	
		r1y = node.y 
		r1z = node.z
		r1w = node.w	
		r1h = node.h
		r1d = node.d
		pygame.draw.line(pygame.display.get_surface(), (255,0,0), (r1x+relx,r1y+rely), (r1x+relx+r1w,r1y+rely))
		pygame.draw.line(pygame.display.get_surface(), (255,0,0), (r1x+relx+r1w,r1y+rely), (r1x+relx+r1w,r1y+rely+r1h))
		pygame.draw.line(pygame.display.get_surface(), (255,0,0), (r1x+relx+r1w,r1y+rely+r1h), (r1x+relx,r1y+rely+r1h))
		pygame.draw.line(pygame.display.get_surface(), (255,0,0), (r1x+relx,r1y+rely+r1h), (r1x+relx,r1y+rely))

	for i in range(0,21):
		if not node.isleaf() and node.nodes and node.nodes.length > 0 and node.nodes.getwithindex(i) != None:
			self.drawrec2(depth-1,node.nodes.getwithindex(i),player)
    

    def draw3(self,player,screen):
	self.result = 0
	self.drawrec3(self.depth,self.tree,player)
	return self.result


    def drawrec3(self,depth,node,player,rotx,roty,rotz):
	px = player.x
	py = player.y
	pz = player.z
	relx = self.room.roomman.room.relativex
	rely = self.room.roomman.room.relativey
	dd = self.depth-1 
	## SE dagonal orientation
	if depth <= 4 and not node.isleaf() and node.nodes.length > 17:
		print "leaf!"
		for i in range(0,21):
			n2 = node.nodes.getwithindex(i)
			for j in range(0,21):
				n1 = node.nodes.getwithindex(j)
				e = engine(rotx,roty,rotz)

				r1 = Vector3(n1.x,n1.y,n1.z)
				r2 = Vector3(n2.x,n2.y,n2.z)
				if rotx:
					r1 = e.mx.multiply(r1)
					r2 = e.mx.multiply(r2)
				if roty:
					r1 = e.my.multiply(r1)
					r2 = e.my.multiply(r2)
				if rotz:
					r1 = e.mz.multiply(r1)
					r2 = e.mz.multiply(r2)
				r1x = r1.array[0]	
				r1y = r1.array[1]	
				r1z = r1.array[2]	
				r2x = r2.array[0]	
				r2y = r2.array[1]	
				r2z = r2.array[2]
				color = (255,0,0)
				if n2.collide or n1.collide:
					color = (0,0,255)
	if node.isleaf():
		r1x = node.x	
		r1y = node.y 
		r1z = node.z
		r1w = node.w	
		r1h = node.h
		r1d = node.d
		pygame.draw.line(pygame.display.get_surface(), (0,255,0), (r1x+relx,r1y+rely), (r1x+relx+r1w,r1y+rely))
		pygame.draw.line(pygame.display.get_surface(), (0,255,0), (r1x+relx+r1w,r1y+rely), (r1x+relx+r1w,r1y+rely+r1h))
		pygame.draw.line(pygame.display.get_surface(), (0,255,0), (r1x+relx+r1w,r1y+rely+r1h), (r1x+relx,r1y+rely+r1h))
		pygame.draw.line(pygame.display.get_surface(), (0,255,0), (r1x+relx,r1y+rely+r1h), (r1x+relx,r1y+rely))
		a = pygame.surfarray.pixels3d(self.image)

		for j in range(0,24):
			for i in range(0,24):
				print "--->%d" % (i)
				c = a[i][j]
				color = (c[0],c[1],c[2])	
				pygame.draw.line(pygame.display.get_surface(),color,(r1x+i+relx,r1y+j+rely),(r1x+i+relx,r1y+j+rely))

	for i in range(0,21):
		if not node.isleaf() and node.nodes.getwithindex(i) != None:
			self.drawrec3(depth-1,node.nodes.getwithindex(i),player,rotx,roty,rotz)

\end{verbatim}
\end{mylisting}


As shown above, you can use less nodes or leaves if you want to but
it will influence your algorithms. Generating the tree uses 21 nodes
or leaves which get a self.depth member variable descending down the 
tree towards a pixel or smallest containing bounding box. If you
cross a node of the tree you can ascend or descend down the tree
via your smallest container e.g. bounding box.

For jumping inside the tree with walls between bounding boxes (nodes)
you can set the depth of the surrounding
nodes (see NOTE2 in the code) which will be set back on jumping down 
or running of a cliff or other terrain feature contained in the tree. 

\begin{wrapfigure}{r}{0.85\textwidth}
\centering
\includegraphics[width=0.85\textwidth]{kq2-screenshot.eps}
\caption{Single 27-tree for grey cliffs and platforms. More trees for
better multi processing towards more terrain features.}
\end{wrapfigure}
\begin{mylisting2}
\begin{verbatim}

# Copyright (C) Johan Ceuppens 2011-2012

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

### This is the code for fig. 1's octrees.
class Room2world(Maproom):
    ""
    def __init__(self, roomman):
        ###Maproom.__init__(self,-320,0)
        ### Maproom.__init__(self,-700,-700)##FIXME1
        Maproom.__init__(self,0,-300,font)##FIXME1
        self.roomman = roomman
        self.player = self.roomman.player
        ###FIXaddonself.octtree = Octtree(500,500,500,300,300,300,1,self)
        self.octtree = Octtree(500,500,500,300,300,300,0,self)
        self.octtree.generatetree(100)
        self.trees.addobject(self.octtree)
        self.octtree = Octtree(1000,400,1000,300,300,300,1,self)
        self.octtree.generatetree(400)
        self.trees.addobject(self.octtree)
\end{verbatim}
\end{mylisting2}
\section{\large Conclusion}

Octrees become 21-trees (or 27-trees or even other trees) which 
develop their own generate and traversal and 3D contained terrain
traversal. Multi core algorithms are faster in 27-trees than in octrees.

\bibliographystyle{plain}
\bibliography{refs} % refs.bib

\end{document}

	
